'''
超内存法,暴力解
'''
# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        count = 0
        for i in data:
            if i == k:
                count = count+1
        return count
'''
二分查找*2
查找第一个这么小的数
查找第一个比这个数大的数
二分查找+remove直到没有这个数 => 超内存
'''
# -*- coding:utf-8 -*-
class Solution2:
    def GetNumberOfK(self, data, k):
        # write code here
        low = 0
        count = 0
        high = len(data) - 1
        while k in data:
            middle = (high + low) // 2
            if data[middle] > k:
                high = middle-1
            if data[middle] < k:
                low = middle + 1
            if data[middle] == k:
                data.remove(data[middle])
                count = count + 1
            print(high)
            count = count + 1
            # 多remove了一次
            data.remove(data[low+1])
            print(data)
        return count
data = [1,2,2,2,2,3,4,5,6]
k = 2
so=Solution2()
print(so.GetNumberOfK(data,k))
'''
没有offer的api法
'''
# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        return data.count(k)
'''
另一种暴力法
'''
# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        if not data:
            return 0
        count = 0
        for i in data:
            if i == k:
                count += 1
        return count